package com.major.sort.shellsorting;

public class ShellSort {

    public static void shellSort(int[] arr) {
        int temp;
        // 分组，增量递减
        for (int step = arr.length / 2; step > 0; step /= 2) {
            // 对分组进行排序；i=step:遍历次数为length-step次
            for (int i = step; i < arr.length; i++) {
                // 交换法
//                for (int j = i - step; j >= 0; j -= step) {
//                    if (arr[j] > arr[j + step]) {
//                        temp = arr[j];
//                        arr[j] = arr[j + step];
//                        arr[j + step] = temp;
//                    }
//                }
                // 移位法
                int j = i;
                temp = arr[j];
                if (arr[j] < arr[j - step]) {
                    while (j - step >= 0 && temp < arr[j - step]) {
                        arr[j] = arr[j - step];
                        j -= step;
                    }
                    arr[j] =temp;
                }
            }
        }
    }
}
